Normally, a computer in an information processing system operates by accessing data items through their location in a memory. Efficient implementation of many computer algorithms require accessing data items through their content. Content-addressable data access can be realized in a variety of different ways. The importance of this problem has stimulated intensive investigations of specialized hardware which includes such exotic technologies such as holography and superconductivity. However, because of technological constraints, memories with content-addressable access, provided by hardware, have found limited applications.
In conventional processors, to access data by means of their content, is executed by software searching techniques. The simplest form of this type of searching technique is a sequential search of the data stored in the memory. In the sequential search method, target key or target data element is retrieved by scanning a memory storing a given collection of data, until data matching the target key is found. Insertions of new data into the given collection of data and deletion of data from the given collection in this type of memory is straight forward. Unfortunately, this method of searching for desired data is too slow for many applications. The most effective methods to date are based on balancing binary trees having a theoretically optimal logarithmic performance. However, this method is very complex and includes a substantial overhead. In the case of an internal memory of a limited size, this overhead prevents this method from enjoying, in practice, the benefits of their theoretical asymptotic optimality.
The information processing unit described herein employs a new method of organization searching procedures based on a lattice data structure. This searching procedure has an extremely simple operational scheme comparable to that of the sequential search. The algorithm principles underlying this information processing unit have been developed by L. Banachowski, A. Kreczmar and W. Ryetec in their book, "Analysis Of Algorithms And Data Structures" published by Addison-Wesley Publishing Company, Workingham England, 1991, using an implicit data structure called a biparental heap.